⟸ Go Back ⟸

Exercise 10 (Homework 1).

(theory of languages)

Simplification of languages

Prove the following equalities between languages:

1. \{w\in \{a,b\}^* \mid aw=wb\}=\emptyset.

2. \{w\in \{a,b\}^* \mid abw=wab\}=\{ab\}^*.

   Warning

   \{ab\}^* is not a typo, there is no “,” between a and b.

3. \{xy\in \{a,b\}^* \mid |x|_a=|y|_a\}=\{w\in \{a,b\}^*\mid |w|_a\in 2\mathbb N\}.

4. \{xy\in \{a,b\}^* \mid |x|_a=|y|_b\}=\{a,b\}^*.

5. \{xy\in \{a,b\}^* \mid |x|_{aa}=|y|_b\}=\{a,b\}^*.

6. \{w\in \{0,1\}^* \mid \mathtt{value}_2(ww^R)\in 3\mathbb N\}=\{0,1\}^*

Note that the set notation \{xy\in A \mid P(x,y)\}, for a set A and a predicate P, is shorthand for \{w\in A \mid \exists x,y\ w=xy \land P(x,y)\}.